The present invention relates generally to data communications networks and more particularly relates to a forwarding table constructed using a combination of HASH table and contents addressable memory (CAM).
Currently, the number of data networks and the volume of traffic these networks carry are increasing at an ever increasing rate. The network devices that make up these networks generally consist of specialized hardware designed to move data at very high speeds. Typical networks, such as Ethernet based networks, are comprised mainly of end stations, Ethernet hubs, switches, routers, bridges and gateways. ATM networks are constructed with similar network devices adapted to carry ATM traffic, e.g., ATM capable end stations, edge devices and ATM switches.
With the ever increasing user demand for faster and faster data communications, network devices must perform at higher and higher speeds. A primary function of a typical network devices is to receive frames (packets, cells, etc.) at one or more ingress ports, and forward the frame to the appropriate egress port. Accomplishing this requires that the network device make a forwarding decision about the received frame. This requires processing resources and typically utilizes a memory lookup operation in making the forwarding decision.
For example, consider a network device with 64 output ports. For each frame received, a forwarding decision must be made to determine which of the output ports to forward the frame to or whether to drop the frame altogether. The decision to forward to one or more ports is indicated in a 64 bit output port vector whereby a bit is set corresponding to each port the frame is to be output to. Assuming that the forwarding decision is made after receipt of the header, than the 64 bit output port vector is stored in a memory queue until the entire frame has been received. Once received, the output port vector is retrieved from memory and the frame is directed to the output ports indicated in the corresponding output port vector.
The memory used to store the output port vector, i.e. the forwarding information, typically utilizes some form of hash table. Hashing techniques are widely used in computer hardware and software systems, such as operating systems, compilers, etc., to store large numbers of elements. Hashing involves calculating an index from a key and using the index to look for matches in a hash table. The function that calculates the index is known as a hash function. The use of hashing permits a plurality of elements to be stored in very large spaces, thus they impose little restriction on the size of the collection of elements stored.
The hash table is well suited for fast storage and retrieval of information elements. The efficiency of a hash table implementation is largely dependent on the hash function used. The keys used by a hash table may be simple or complex, which in the latter case may be made up of several attributes of an element. Alternatively, the complete element may be used as the input to the hash function.
A block diagram illustrating an example hash table implementation some of the entries of which have one or more collisions associated therewith is shown in FIG. 1. The hash table, generally referenced 10, comprises a table 19 having a plurality of entries 12. In this example, the table 19 comprises 10 entries. The input (known as the key) is applied to the hash function 18. The function takes the key and xe2x80x98hashesxe2x80x99 it wherein it returns an index (possibly a large integer) obtained by manipulating the key. The index generated by the hash function is then applied to the hash table 19.
With a good hash function, all the bits in the key affect the value of the index generated. In addition, the dependence of the index on the value of the key is preferably non-obvious.
The principle of a hash table is that a possibly infinite set of elements is partitioned into a finite number of hash values. The hash function is performed using the key as input to yield a resulting hash value (i.e. index). A hash collision occurs, however, if for two different keys the hash function returns the same hash value. In such cases, a collision list is generated whereby all the keys that return the same hash value are linked.
For example, with reference to FIG. 1, the hash function 18 calculates the index from the key by (1) transforming the key into an integer according to its position in the alphabet, (2) the resulting integers are added together and (3) the result is divided by the size of the hash table (i.e. 10) and the remainder is the hash result or index.
Thus, the key xe2x80x98cdfxe2x80x99 is hashed to the value 3. The key xe2x80x98noxe2x80x99 is hashed to the value 9. A first collision occurs when hashing the key xe2x80x98efhxe2x80x99. As a result, both keys are placed in a collision linked list that is associated with table entry 9. A second collision occurs on the key xe2x80x98cccxe2x80x99 and as a result, this key is added to the collision linked list associated with hash table entry 9. Note that each entry and associated linked list is commonly called a bucket. Upon retrieval, the linked list associated with a hash result is searched element by element for a match with the key. If the indexes obtained by hashing are uniformingly distributed across the array of buckets, then the buckets are not likely to be long.
Thus, in the ideal case, a hash function returns a different hash value for each unique key. If there are collisions, it is preferable that the collision linked list remains small in order to maintain fast access time. This means that hash values should be evenly distributed across all the hash table entries. In addition, the hash function preferably always returns the same hash value for a given key.
Note that in many applications, a hash table is better at retrieving information that an array or a linked list since the correct bucket is away determined very quickly using hashing. Then, if there were one or more collisions, only the few keys that collided at the index of the bucket must be searched.
Thus, choosing a good peforming hashing function h(k) is the tricky part of implementing a hash table based search and retrieval system. The function h should ideally distribute the input elements as uniformly as possible over the buckets (or slots) of the hash table. The major criterion is that the hash function should generate a minimum number of collisions.
If the probability that a key k occurs in the set of input value is P(k), and there are m slots in the hash table, then a uniform hashing function h(k) satisfies:                                           ∑                                          k                |                                  h                  ⁡                                      (                    k                    )                                                              =              0                                ⁢                      xe2x80x83                    ⁢                      P            ⁡                          (              k              )                                      =                                            ∑                                                k                  |                                      h                    ⁡                                          (                      k                      )                                                                      =                1                                      ⁢                          xe2x80x83                        ⁢                          P              ⁡                              (                k                )                                              =                      …            =                                                            ∑                                                            k                      |                                              h                        ⁡                                                  (                          k                          )                                                                                      =                                          m                      -                      2                                                                      ⁢                                  xe2x80x83                                ⁢                                  P                  ⁡                                      (                    k                    )                                                              =                                                                    ∑                                                                  k                        |                                                  h                          ⁡                                                      (                            k                            )                                                                                              =                                              m                        -                        1                                                                              ⁢                                      xe2x80x83                                    ⁢                                      P                    ⁡                                          (                      k                      )                                                                      =                                  1                  m                                                                                        (        1        )            
Most of the time it is not possible to ensure this. Thus, a uniform hashing function is difficult to achieve in practice.
A hash table is realized using a large enough memory to store the hashed index values in a one way organization. The hashing function hashes the key to a smaller index. In a network device application, the key comprises a MAC address, for example. The index is used to access a linear table called the hash table. The MAC address is stored at a location corresponding to the index along with the forwarding information. In the event of a collision, a sequential search is performed of the collision linked list associated with that location. A hit occurs when the index matches the stored data.
The advantage of using a hash table is its relatively low cost in terms of size required to store a given number of entries. A disadvantage of a hash table with a collision linked list is the multiple cycles required for finding a hit. Limiting the number of addresses per hash entry is likely to result in one or more addresses not being able to be stored, resulting in a less than 100% hit ratio.
The present invention solves the problems associated with the prior art by providing a forwarding table comprising a combination of a hash table and a content addressable memory (CAM). The advantages of both a hash table and a CAM are combined in the forwarding table of the present invention. The forwarding table combines a one way hash table and a small CAM to perform the forwarding information retrieval function. The data stored in the hash table is limited to one MAC address per entry thus eliminating the additional time required to search a collision linked list in the event multiple keys hash to the same entry in the hash table.
When MAC addresses are being added to the forwarding table, they are first tried in the hash table. The key (i.e. MAC address) is applied to the hash function and a resulting index input to the hash table. If a hit occurs, it indicates that an entry at that index already exists and a location in the CAM is then allocated for that address. As long as the CAM does not become full, a 100% hit rate is guaranteed.
The hash function utilizes one or more hashing polynomials to perform polynomial division of the key. The results of the polynomial division are used to generate an output index. The index is used to retrieve a corresponding entry in the hash table. In parallel, the key is also applied to the CAM.
During retrieval of forwarding information from the forwarding table, one of the two outputs from the hash table and the CAM forms the forwarding information that is output to the next processing stage. A forward pointer select circuit generates the select signal to a multiplexer whose inputs comprise the outputs of the hash table and CAM. Either the hash table or the CAM generates a hit but not both. Thus, if the hash table generates a hit, the multiplexer selects the forwarding information generated by the hash table as the output forwarding information. On the other hand, if the CAM generates a hit, the multiplexer selects the forwarding information generated by the CAM as the output forwarding information.
There is thus provided in accordance with the present invention a table for storing and retrieving a plurality of elements comprising a hash function operative to generate an index in accordance with a key input thereto, a hash table having a plurality of entries and adapted to store the elements in accordance with their corresponding indexes, a content addressable memory (CAM) operative to store the elements in accordance with their content, storing means for adding an element to the table, the storing means operative to apply the element as an input key to the hash function and to generate an index in response thereto, apply the index to the hash table, and in the event of a miss, write the element to the hash table, and in the event of a hit, allocate a location in the CAM and store the element therein and retrieving means for retrieving an element from the table in accordance with an input key, the retrieving means operative to apply the key to the hash function and generate an index in response thereto, apply the index to the hash table and use the element generated in the event of a hit and apply the key to the CAM and use the element generated in the event of a hit.
There is also provided in accordance with the present invention a forwarding table for storing and retrieving forwarding information based on Media Access Code (MAC) addresses comprising a hash function operative to generate an index in accordance with a MAC address key input thereto, a hash table for storing forwarding information in accordance with corresponding MAC addresses, a content addressable memory (CAM) operative to store forwarding information in accordance with MAC addresses, storing means for adding a MAC address entry to the forwarding table, the storing means operative to apply the MAC address as an input key to the hash function and to generate an index in response thereto, apply the index to the hash table and in the event of a miss, write forwarding information corresponding to the MAC address to the hash table, and in the event of a hit, allocate a location in the CAM and store the forwarding information corresponding to the MAC address therein and retrieving means for retrieving forwarding information from the forwarding table in accordance with a MAC address key, the retrieving means operative to apply the key to the hash function and generate an index in response thereto, apply the index to the hash table and use the forwarding information generated in the event of a hit and apply the key to the CAM and use the forwarding information generated in the event of a hit.
There is further provided in accordance with the present invention a method of storing and retrieving forwarding information based on Media Access Code (MAC) addresses in a forwarding table, the method comprising the steps of generating an index using a hashing function and in accordance with a MAC address key input thereto, storing forwarding information in accordance with corresponding MAC addresses in a hash table, storing forwarding information in accordance with MAC addresses in a content addressable memory (CAM), adding a MAC address entry to the forwarding table by applying the MAC address as an input key to the hash function and generating an index in response thereto, applying the index to the hash table, and in the event of a miss, writing forwarding information corresponding to the MAC address to the hash table, and in the event of a hit, allocating a location in the CAM and storing the forwarding information corresponding to the MAC address therein and retrieving forwarding information from the forwarding table in accordance with a MAC address key by applying the key to the hash function and generating an index in response thereto, applying the index to the hash table and using the forwarding information generated in the event of a hit and applying the key to the CAM and using the forwarding information generated in the event of a hit.